package nowcode;

import org.apache.commons.lang3.StringUtils;
import org.junit.Test;

public class LongestPalindromeTest {

    String originString = "abcda";
    int max = 0;
    String longestPalindrome = StringUtils.EMPTY;

    /**
     * @desc: 中心扩散法  O(N^2)
     * @method: CentralDiffusion
     * @param: []
     * @return: void
     * @auther: zhipingzhang
     * @date: 2019/5/18 19:05
     */
    @Test
    public void CentralDiffusion() {
        char[] chars = originString.toCharArray();
        if (chars.length > 0) {
            max = 1;
            longestPalindrome = originString.substring(0, 1);
        }
        for (int i = 0; i < chars.length - 1; i++) {
            //判断单核长度
            findLongString(chars, i - 1, i + 1, 1);
            //判断双核长度
            findLongString(chars, i, i + 1, 0);
        }
        System.out.println(max);
        System.out.println(longestPalindrome);
    }

    private void findLongString(char[] chars, int low, int high, int tempMax) {
        while (low >= 0 && high < chars.length) {
            if (chars[low] == chars[high]) {
                tempMax = tempMax + 2;
            } else {
                break;
            }
            if (tempMax > max) {
                max = tempMax;
                longestPalindrome = originString.substring(low, high + 1);
            }
            low--;
            high++;
        }
    }
}
